package me.algo.sc;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * @author guozheng
 * @date 2024/4/16
 */
public class SC220 {
    public static void main(String[] args) {
        int[] nums =
                {1, 2, 3, 1};
        var indexDiff = 3;
        var valueDiff = 0;
        System.out.println(containsNearbyAlmostDuplicate1(nums, indexDiff, valueDiff));
    }

    /**
     * 给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。
     * <p>
     * 找出满足下述条件的下标对 (i, j)：
     * <p>
     * i != j,
     * abs(i - j) <= indexDiff
     * abs(nums[i] - nums[j]) <= valueDiff
     * 如果存在，返回 true ；否则，返回 false 。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
     * 输出：true
     * 解释：可以找出 (i, j) = (0, 3) 。
     * 满足下述 3 个条件：
     * i != j --> 0 != 3
     * abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
     * abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0
     * 示例 2：
     * <p>
     * 输入：nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
     * 输出：false
     * 解释：尝试所有可能的下标对 (i, j) ，均无法满足这 3 个条件，因此返回 false 。
     *
     * @param nums
     * @param indexDiff
     * @param valueDiff
     * @return
     */
    public static boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        if (Objects.isNull(nums) || nums.length <= 1) {
            return false;
        }
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            for (int k = Math.min(i + indexDiff, len); k > i; k--) {
                if (Math.abs(nums[k] - nums[i]) <= valueDiff) {
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean containsNearbyAlmostDuplicate1(int[] nums, int indexDiff, int valueDiff) {
        if (Objects.isNull(nums)) {
            return false;
        }
        HashMap<Integer, HashMap<Integer, Integer>> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int val = nums[i];
            int bucket = val / (valueDiff + 1);
            HashMap<Integer, Integer> vmp = map.getOrDefault(bucket, new HashMap<Integer, Integer>());
            vmp.put(i, val);
            map.put(bucket, vmp);
        }
        for (int i = 0; i < nums.length; i++) {
            int val = nums[i];
            int bucket = val / (valueDiff + 1);
            HashMap<Integer, Integer> vmp = map.getOrDefault(bucket, new HashMap<Integer, Integer>());
            for (int j = i + 1; j <= i + indexDiff; j++) {
                boolean b = vmp.containsKey(j);
                if (b) {
                    return true;
                }
            }

        }
        return false;
    }

    public boolean containsNearbyAlmostDuplicate2(int[] nums, int indexDiff, int valueDiff) {
        int n = nums.length;
        Map<Long, Long> map = new HashMap<>();
        long size = valueDiff + 1L;
        for (int i = 0; i < n; i++) {
            long u = nums[i];
            long idx = getIdx(u,size);
            // 目标桶已存在（桶不为空），说明前面已有 [u - t, u + t] 范围的数字
            if (map.containsKey(idx)) return true;
            // 检查相邻的桶
            long l = idx - 1, r = idx + 1;
            if (map.containsKey(l) && u - map.get(l) <= valueDiff) return true;
            if (map.containsKey(r) && map.get(r) - u <= valueDiff) return true;
            // 建立目标桶
            map.put(idx, u);
            // 移除下标范围不在 [max(0, i - k), i) 内的桶
            if (i >= indexDiff) map.remove(getIdx(nums[i - indexDiff], size));
        }
        return false;
    }

    long getIdx(long u, long size) {
        return u >= 0 ? u / size : ((u + 1) / size) - 1;
    }


}
